package basis.netease.medium;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.TreeSet;

/**
 * 7-15 存在重复元素3
 * 给你一个整数数组 nums 和两个整数 indexDiff 和 valueDiff 。
 * 找出满足下述条件的下标对 (i, j)：
 * i != j
 * abs(i - j) <= indexDiff
 * abs(nums[i] - nums[j]) <= valueDiff
 * 如果存在，返回 1 ；否则，返回 0
 * 提示:
 * 2 <= nums.length <= 10^5
 * -10^9 <= nums[i] <= 10^9
 * 1 <= indexDiff <= nums.length
 * 0 <= valueDiff <= 10^9
 * 运行有时间和内存限制
 * 输入格式:
 * 字符串，包括3部分：数组nums、indexDiff、valueDiff，每部分用英文逗号分隔。
 * 其中，数组nums的每个元素用空格分隔。
 * 输出格式:
 * 0 or 1
 * 输入样例1:
 * 在这里给出一组输入。例如：
 * 1 2 3 1,3,0
 * 输出样例1:
 * 在这里给出相应的输出。例如：
 * 1
 * 解释：可以找出 (i, j) = (0, 3) 。满足下述 3 个条件：
 * i != j --> 0 != 3
 * abs(i - j) <= indexDiff --> abs(0 - 3) <= 3
 * abs(nums[i] - nums[j]) <= valueDiff --> abs(1 - 1) <= 0
 * 输入样例2:
 * 在这里给出一组输入。例如：
 * 1 5 9 1 5 9,2,3
 * 输出样例2:
 * 在这里给出相应的输出。例如：
 * 0
 * 解释：尝试所有可能的下标对 (i, j) ，均无法满足这 3 个条件，因此返回 0
 */
public class Main_12 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] input = scanner.nextLine().split(",");
        String[] numsStr = input[0].split(" ");
        int indexDiff = Integer.parseInt(input[1]);
        int valueDiff = Integer.parseInt(input[2]);
        int length = numsStr.length;
        int[] nums = new int[length];
        for (int i = 0; i < length; i++) {
            nums[i] = Integer.parseInt(numsStr[i]);
        }
        System.out.println(existNear(nums, indexDiff, valueDiff) ? "1" : "0");
    }

    /**
     * 最简单的方法
     * 能过所有用例
     */
    public static boolean existNear(int[] nums, int indexDiff, int valueDiff) {
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j <= i + indexDiff && j < len; j++) {
                if (Math.abs(nums[i] - nums[j]) <= valueDiff) {
                    return true;
                }
            }
        }
        return false;
    }


    /**
     * 能过所有用例
     */
    static boolean existNear2(int[] nums, int indexDiff, int valueDiff) {
        // 因为 -valueDiff <= nums[j] - nums[i] <= valueDiff。所以可以推导出nums[i] - valueDiff <= nums[j] <= nums[i] + valueDiff
        TreeSet<Integer> win = new TreeSet();
        for (int i = 0; i < nums.length; i++) {
            Integer ceiling = win.ceiling(nums[i] - valueDiff);
            if (ceiling != null && ceiling <= nums[i] + valueDiff) {
                return true;
            }
            // 滑动窗口：保证TreeSet数量少于indexDiff数量；一旦i大于indexDiff，就移除最开始进入的元素
            win.add(nums[i]);
            if (i >= indexDiff) {
                win.remove(nums[i - indexDiff]);
            }
        }
        return false;
    }

    /**
     * 理论上该方法比TreeSet更快，但是用例有问题，部分超时
     */
    static boolean existNear3(int[] nums, int indexDiff, int valueDiff) {
        // 桶的大小，加1是因为valueDiff可能是0
        int bucketSize = valueDiff + 1;
        // key: 桶的编号，value: 最近加入桶的元素的下标
        Map<Integer, Integer> buckets = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int bucketNum = nums[i] / bucketSize;
            // 同一桶内元素，必定满足-valueDiff <= nums[j] - nums[i] <= valueDiff
            if (buckets.containsKey(bucketNum)) {
                return true;
            }
            // 相邻的桶也有可能满足-valueDiff <= nums[j] - nums[i] <= valueDiff
            if ((buckets.containsKey(bucketNum - 1) && Math.abs(nums[i] - nums[buckets.get(bucketNum - 1)]) <= valueDiff) ||
                    (buckets.containsKey(bucketNum + 1) && Math.abs(nums[i] - nums[buckets.get(bucketNum + 1)]) <= valueDiff)) {
                return true;
            }
            // 滑动窗口：保证Map数量少于indexDiff数量；一旦i大于indexDiff，就移除最开始进入的元素
            buckets.put(bucketNum, i);
            if (i >= indexDiff) {
                int removeBucketNum = nums[i - indexDiff] / bucketSize;
                buckets.remove(removeBucketNum);
            }
        }
        return false;
    }

}
